import java.util.Arrays;
import java.util.Random;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: qian
 * Date: 2022-10-26
 * Time: 17:07
 */

interface Speak {
    void speak();
}
class Cat implements Speak {
    public void speak() { System.out.println("meow"); }
}
class Dog implements Speak {
    public void speak() { System.out.println("woof"); }
}
class Bird implements Speak {
    public void speak() { System.out.println("chirrup"); }
}
class test
{
    public static void main(String[] args) {
//        Speak[] pets = new Speak[]{ new Cat(), new Dog(), new Bird() };
//        for(Speak pet : pets)
//            pet.speak();
        String a="";
        System.out.println(a.concat("hello"));

    }
}
public class Test {
    public static void swap(int[] array,int i,int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    public static int partition(int[] arr, int left,int right) {
        int cur = left+1;
        int prev = left;
        int priot = arr[left];
        while(cur <= right) {
//            if(arr[cur] < priot && (prev+1) != cur) {
//                prev++;
//                swap(arr,prev,cur);
//            }
            if(arr[cur] < priot && ++prev != cur) {
                swap(arr,prev,cur);
            }

            cur++;
        }
        swap(arr,left,prev);
        return prev;
    }
    public static void quick(int[] array) {
        int begI = 0;
        int endI = array.length-1;
        QuickSort(array,begI,endI);
    }
    public static void QuickSort(int[] array, int begI, int endI) {
        if(begI >= endI) {
            return;
        }
        int benchmark = partition(array,begI,endI);
        QuickSort(array,begI,benchmark-1);
        QuickSort(array,benchmark+1,endI);
    }

    public static void main(String[] args) {
        int[] arr={3,2,1,5,6,7,9,8};
        quick(arr);
        System.out.println(Arrays.toString(arr));
    }
}
